#include <stdio.h>
#include <stdlib.h>
//#include "prng.c"

#define K 1
#define L2 1000
#define ALFA 0.1
#define INSTANCIA "teste.txt"

/*
1 - vamo gerar aleatoriamente uma solucao valida para o problema
2 - com essa solucao vamos aleatoriamente escolher uma das seguintes operacoes: insercao de estacao, remocao de estacao ou permutacao de estacao. para gerar um vizinho de solucao valida e calcular seu custo e compara-lo com o menor custo que jah temos
3 - com o vizinho vamos gerar, usando uma das 3 operacoes citadas anteriormente, e gerar outro vizinho e comparar seu custo com o da custo da solucao q gerou esse vizinho (solucao gerada no passo 2), vamos fazer esse processo entre 100 ~ 1000 vezes.
4 - terminada as 100 ~ 1000 iteracoes do passo 3 vamos comparar a menor solucao encontrada nesse caminho e compara-lo com a menor solucao que jah temos.
5 - abaixamos a temperatura
6 - volta para passo 1.
*/


int main(){
    //parametros auxiliares
    double aleatorio;
    int i, j;
    char prox_char = '\n';
    FILE *fin = fopen(INSTANCIA, "r");
    fpos_t file_position;
    
    //parametros do simulated annealing
    double temp = 1;
    int* sol_inicial;
    int* sol_gerada; //basicamente, o nosso S' vizinho da solucao inicial
    int* sol_melhor;
    double delta_custo, probabilidade;

    //estrutura para a leitura da instancia
    int n; //numero de pontos a serem cobertos
    int m; //numeros de estacoes de emissao
    typedef struct{
            int ponto;
            struct Cobertura *prox;
            } Cobertura;
    double *custo_estacao;
    Cobertura *cobertura;
    Cobertura *aux;

    //leitura da instancia e construcao dos dados
    fscanf(fin, " %*c %d", &n);  //leitura da primeira linha
    fscanf(fin, " %*c %d", &m);  //leitura da segunda linha
    fscanf(fin, "%*c");

    sol_inicial = malloc(m*sizeof(int));
    sol_gerada = malloc(m*sizeof(int));
    sol_melhor = malloc(m*sizeof(int));
    custo_estacao = malloc(m*sizeof(double));
    cobertura = malloc(m*sizeof(Cobertura));

    for(i=0; i<m; i++){
      fscanf(fin, "%c", &prox_char);
      fscanf(fin, "%d", &j);
      fscanf(fin, " %lf", &custo_estacao[i]); //le o trecho "S_i C_i" e atribui o valor C_i no vetor custo
      aux = &cobertura[i];
      do{
	fscanf(fin, " %d", &aux->ponto);
	fscanf(fin, "%c", &prox_char); 
	fgetpos(fin, &file_position);
	fscanf(fin, "%c", &prox_char);
	if(prox_char != '\n'){
	  fsetpos(fin, &file_position);
	  aux->prox = malloc(sizeof(Cobertura));
	  aux = aux->prox;
	} else aux->prox = NULL; 
      }while(prox_char != '\n');
    } //for

    
    //simulated annealing
    while (temp > 0){
      //gerar solucao inicial aleatoriamente
      sol_inicial = gerar_solucao_inicial(n, m, cobertura);

      for(i=0; i < L2; i++){
	//gerar um vizinho a partir da solucao inicia e calcular o seu custo
	sol_gerada = vizinho(n, m, sol_inicial, cobertura);
            
	//calculo da diferenca de custo
	delta_custo = custo(m, sol_gerada, custo_estacao) - custo(m, sol_inicial, custo_estacao);
            
	//verificar se aceita a solucao gerada
	if(delta_custo < 0){
	  for(j=0; j < m ;j++) sol_inicial[j] = sol_gerada[j];
	  if(custo(m, sol_gerada, custo_estacao) < custo(m, sol_melhor, custo_estacao)){
	    for(j=0; j < m; j++) sol_melhor[j] = sol_gerada[j];
	  }
	} else {
	  aleatorio = prng_get_double();
	  probabilidade = ((double) 1)/exp(delta_custo / (K*temp));
	  if(aleatorio <= probabilidade){
	    for(j=0; j < m; j++) sol_inicial[j] = sol_gerada[j];
	  }
	}
      }//for (L2)
      temp = temp - ALFA;
    }//while (L1, ou temp)
    
    //impressao da melhor solucao encontrada
    imprime_solucao(m, sol_melhor, custo_estacao);
    fclose(fin);
    return 0;
}
